#pragma once

#include <crane/defs.hpp>
#include "detail/rev_iter.hpp"

CARBON_NS_BEGIN
namespace detail {


struct ListNodeBase {
    ListNodeBase * prev;
    ListNodeBase * next;

    void pop() { // pop from list
        prev->next = next;
        next->prev = prev;
        next = prev = nullptr;
    }
};

template <class T>
struct ListNode : ListNodeBase {
    using ValueType = T;

    T value;
};


template<class T>
struct ListIterator 
{
    using ValueType = T;
    using PointType = T *;
    using ReferenceType = T&;

    ListNodeBase *       m_pnode;

    ListIterator() : m_pnode(nullptr) {}
    ListIterator(ListNodeBase * pnode) : m_pnode(pnode) {}

    ValueType & operator*() { return static_cast<ListNode<T>*>(m_pnode)->value; }
    ValueType * operator->() { return &static_cast<ListNode<T>*>(m_pnode)->value; }
    const ValueType & operator*() const { return static_cast<ListNode<T>*>(m_pnode)->value; }
    const ValueType * operator->() const { return &static_cast<ListNode<T>*>(m_pnode)->value; }
    ListConstIterator & operator++() { m_pnode = m_pnode->next; return *this; }
    ListConstIterator & operator--() { m_pnode = m_pnode->prev; return *this; }
    ListConstIterator operator++(int) const   { auto tmp = *this; m_pnode = m_pnode->next; return tmp;  }
    RListConstIterator operator--(int) const   { auto tmp = *this; m_pnode = m_pnode->prev; return tmp;  }
    bool operator==(const ListIterator & other) const { return this->m_pnode == other.m_pnode; }
    bool operator!=(const ListIterator & other) const { return this->m_pnode != other.m_pnode; }
};

template<class T>
struct ListConstIterator 
{
    using ValueType = T;
    using PointType = T *;
    using ReferenceType = T &;

    const ListNodeBase * m_pnode;

    ListIterator() : m_pnode(nullptr) {}
    ListIterator(ListNodeBase * pnode) : m_pnode(pnode) {}

    const ValueType & operator*() const { return static_cast<ListNode<T>*>(m_pnode)->value; }
    const ValueType * operator->() const { return &static_cast<ListNode<T>*>(m_pnode)->value; }
    ListConstIterator & operator++() { m_pnode = m_pnode->next; return *this; }
    ListConstIterator & operator--() { m_pnode = m_pnode->prev; return *this; }
    ListConstIterator operator++(int) const   { auto tmp = *this; m_pnode = m_pnode->next; return tmp;  }
    RListConstIterator operator--(int) const   { auto tmp = *this; m_pnode = m_pnode->prev; return tmp;  }
    bool operator==(const ListIterator & other) const { return this->m_pnode == other.m_pnode; }
    bool operator!=(const ListIterator & other) const { return this->m_pnode != other.m_pnode; }
};


struct ListImpl {
    size_t          m_size;
    ListNodeBase    m_head;

    ListImpl() { this->init(); }

    void init() {
        m_size = 0;
        m_head.next = &m_head;
        m_head.prev = &m_head;
    }

    size_t size() const { return m_size; }

    ListNodeBase * begin() { return m_head.next; }
    ListNodeBase * end() { return &m_head; }

    const ListNodeBase * cbegin() const { return m_head.next; }
    const ListNodeBase * cend() const { return &m_head; }

    void  insert(ListNodeBase * pos, ListNodeBase * node) {
        node->next = pos;
        node->prev = pos->prev;
        pos->prev->next = node;
        pos->next->prev = node;
    }

}; // ListImpl



} // namespace detail;

template<class T, class Allocator>
class List {
public:
    using NodeType = detail::ListNode<T>;    
    using ValueType = T;
    using AllocType = typename Allocator::rebind<NodeType>;
    using Iterator = detail::ListIterator<T, NodeType>;
    using ConstIterator = detail::ConstListIterator<const T, NodeType>;
    using RevIterator = RevIterator<Iterator>;
    using ConstRevIterator = RevIterator<ConstIterator>;

private:
    detail::ListImpl m_impl;

public:
    List() : size_(0) {}
    List(AllocType alloc) : impl_(std::move(alloc)) {}
    List(const List & other) : impl_(other.m_impl) {}
    List(List && other) : impl_(std::move(other.m_impl)) {}
    ~List() CRANE_NO_EXCEPT {}

    List & operator=(const List & other) { impl_ = other.m_impl; }
    List & operator=(List && other) {
        if ( this != &other) m_impl = std::move(other.m_impl);
        return *this;
    }

    size_t size() const { return m_impl->size_; }
    bool   empty() const { return m_impl->size_ == 0; }

    ValueType & front() { return static_cast<NodeType*>(m_impl->root_.next)->value; }
    ValueType & back()  { return static_cast<NodeType*>(m_impl->root_.prev)->value; }

    const ValueType & front() const { return static_cast<NodeType*>(m_impl->root_.next)->value; }
    const ValueType & back() const  { return static_cast<NodeType*>(m_impl->root_.prev)->value; }

    Iterator begin() { return Iterator(&m_impl->root_, m_impl->root_.next); }
    Iterator end()   { return Iterator(&m_impl->root_, &m_impl->root_); }

    ConstIterator begin() const { return Iterator(&m_impl->root_, m_impl->root_.next); }
    ConstIterator end() const { return Iterator(&m_impl->root_, &m_impl->root_); }

    RevIterator rbegin() { return RevIterator(&m_impl->root_, m_impl->root_.prev); }
    RevIterator rend()   { return RevIterator(&m_impl->root_, &m_impl->root_); }

    ConstRevIterator rbegin() const { return RevIterator(&m_impl->root_, m_impl->root_.prev); }
    ConstRevIterator rend() const { return RevIterator(&m_impl->root_, &m_impl->root_); }

    void pushFront(const ValueType & value) { insert(begin(), value); } 
    void pushBack(const ValueType & value)  { insert(end(), value); }

    void pushFront(ValueType && value) { insert(begin(), std::move(value)); }
    void pushBack(ValueType && value)  { insert(end(), std::move(value)); }

    void insert(Iterator pos, const ValueType & value);
    void insert(Iterator pos, ValueType && value);

    void popFront() { erase(begin()); }
    void popBack()  { erase(--end()); }

    void erase(Iterator pos) CRANE_NO_EXCEPT;

    void clear() CRANE_NO_EXCEPT;

    void swap(List & other);

}; // List


template<class T, class Allocator>
void List<T, Allocator>::insert(Iterator pos, const ValueType & value) 
{
    NodeType * pnode = m_impl.alloc_.allocate(sizeof(NodeType));
    m_impl.alloc_.construct(&pnode->value, value);
    pnode->next = pos.node_;
    pnode->pref = pos.node_->prev;
    pos.node_->prev->next = pnode;
    pos.node_->prev = pnode; 
}

template<class T, class Allocator>
void List<T, Allocator>::insert(Iterator pos, ValueType && value) 
{
    NodeType * pnode = m_impl.alloc_.allocate(sizeof(NodeType));
    m_impl.alloc_.construct(&pnode->value, std::move(value));
    pnode->next = pos.node_;
    pnode->pref = pos.node_->prev;
    pos.node_->prev->next = pnode;
}

template<class T, class Allocator>
void List<T, Allocator>::erase(Iterator pos) CRANE_NO_EXCEPT
{
    NodeType * pnode = pos.node_;
    pnode->prev->next = pnode->next;
    pnode->next->prev = pnode->prev;
    m_impl.alloc_.destroy(&pnode->value);
    m_impl.alloc_.deallocate(pnode);
}

template<class T, class Allocator>
void List<T, Allocator>::clear() CRANE_NO_EXCEPT
{
    NodeType * pnode = m_impl->root_.next;
    while (pnode != &m_impl->root_) {
        NodeType * tmp = pnode;
        pnode = pnode->next;
        m_impl.alloc_.destroy(tmp->value);
        m_impl.alloc_.deallocate(tmp);
    }
    m_impl->root_.next = &m_impl->root_;
    m_impl->root_.prev = &m_impl->root_;
}

template<class T, class Allocator>
void List<T, Allocator>::swap(List & other)  
{
    ListNodeBase tmp;
    tmp.next = m_impl->root_.next;
    tmp.prev = m_impl->root_.prev;

    m_impl->root_.next = other.m_impl->root_.next;
    m_impl->root_.prev = other.m_impl->root_.prev;

    other.m_impl->root_.next = tmp.next;
    other.m_impl->root_.prev = tmp.prev;
}


CARBON_NS_END
